package test.niuke;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by linshuo on 2018/2/25.
 */
public class JumpFloorBinTree {
    private static class Node {
        private int val;
        private int deep;
        private Node leftChild;
        private Node rightChild;

        public Node(int val) {
            this.val = val;
        }

        public int getDeep() {
            return deep;
        }

        public void setDeep(int deep) {
            this.deep = deep;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public Node getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(Node leftChild) {
            this.leftChild = leftChild;
        }

        public Node getRightChild() {
            return rightChild;
        }

        public void setRightChild(Node rightChild) {
            this.rightChild = rightChild;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", deep=" + deep +
                    ", leftChild=" + leftChild +
                    ", rightChild=" + rightChild +
                    '}';
        }
    }

    /**
     * 建立最大深度为layerNum的满二叉树 (根节点的深度为0)
     *
     * @param deep 最大深度
     * @return
     */
    public Node createBinTree(int deep) {
        Node rootNode = new Node(0);
        rootNode.setDeep(0);
        List<Node> curLayerNodes = new ArrayList<>();
        curLayerNodes.add(rootNode);
        for (int i = 0; i < deep; i++) {
            List<Node> tempLayerNodes = new ArrayList<>();
            for (Node node : curLayerNodes) {
                Node leftNode = new Node(1);
                leftNode.setDeep(node.getDeep() + 1);
                Node rightNode = new Node(2);
                rightNode.setDeep(node.getDeep() + 1);
                node.setLeftChild(leftNode);
                node.setRightChild(rightNode);
                tempLayerNodes.add(leftNode);
                tempLayerNodes.add(rightNode);
            }
            curLayerNodes.clear();
            curLayerNodes.addAll(tempLayerNodes);
        }
        return rootNode;
    }

    /**
     * 二叉树的先序遍历
     *
     * @param node
     */
    public void traverse(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        traverse(node.getLeftChild());
        traverse(node.getRightChild());
    }

    public static void main(String[] args) {
        JumpFloorBinTree binTree = new JumpFloorBinTree();
        Node rootNode = binTree.createBinTree(5);
        binTree.traverse(rootNode);

    }
}
